import java.util.LinkedList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
 */
class Solution2 {
    public List<Integer> findAnagrams(String s, String p) {
        int n = p.length(), count = 0;
        char[] ch1 = s.toCharArray(), ch2 = p.toCharArray();
        int[] hashS = new int[26], hashP = new int[26];
        List<Integer> ret = new LinkedList<>();

        // 把p统计进hash2中
        for(int i = 0; i < n; i++) {
            int tmp = ch2[i] - 'a';
            hashP[tmp] += 1;
        }

        for(int left = 0, right = 0; right < s.length(); right++) {
            // 1、进窗口
            int cur = ch1[right] - 'a';
            hashS[cur] += 1;
            // 统计有效字符的个数
            if(hashS[cur] <= hashP[cur]) count++;
            // 2、判断
            if(right - left + 1 == n) {
                int tmp = ch1[left] - 'a';
                // 3、更新结果
                if(count == n) ret.add(left);
                // 维护有效字符的个数
                if(hashS[tmp] <= hashP[tmp]) count--;
                // 4、出窗口
                hashS[tmp]--;
                left++;
            } 
        }

        return ret;
    }
}